#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

bool search(vector<int> &nums, int target) {
    int low = 0;
    int high = nums.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (nums[mid] == target)
            return true;
            //2,5,6,0,0,1,2
            //说明右边这有序
        else if (nums[mid] < nums[high]) {
            //说明可能在右半部分
            if (nums[mid] < target && nums[high] >= target)
                low = mid + 1;
            else
                high = mid - 1;//很明显mid不是-1得

            //说明左半部分有序
        } else if (nums[mid] > nums[high]) {
            if (nums[mid] > target && nums[low] <= target) {
                //说明在区间里面
                high = mid - 1;
            } else
                low = mid + 1;
        } else {
            high--;
            //这里不能low++ 这边是右侧去重 因为判断的都是mid值和high 比较的所以得右边去重high--;
        }


    }


    return false;

}